package heap;

/**
 * description:
 * author:张腾
 * date:2021-04-08
 */

/**
 * 堆的排序
 * 构造小根堆，再进行遍历删除操作，即是从小到大获取了
 */
public class HeapSort {

    //判断heap堆中i索引处的值是否小于索引j处的值
    private static boolean less(Comparable[] heap,int i,int j){
        return heap[i].compareTo(heap[j])<0;
    }

    //交换heap堆中i索引和j索引处的值
    private static void exch(Comparable[] heap,int i,int j){
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    //根据原数组source，构造出堆heap
    private static void createHeap(Comparable[] source,Comparable[] heap){
        //把source中的元素拷贝到heap中，heap中的元素就构成一个无序的堆
        System.arraycopy(source,0,heap,1,source.length);

        //对堆中的元素进行下沉调整（从长度一半开始，往索引1处扫描） ，因为长度一半以前的元素才拥有子节点
        for (int i = (heap.length)/2;i > 0;i --){
            sink(heap,i,heap.length-1);
        }
    }

    //对source数组的数据从小到大排序
    public static void sort(Comparable[] source){
        //构建堆
        Comparable[] heap = new Comparable[source.length+1];
        createHeap(source,heap);
        //记录未排序的元素中最大的元素
        int N = heap.length-1;
        while (N!=1){
            exch(heap,1,N);
            //排除交换后最大元素所在的索引，不用参与下沉
            N--;
            sink(heap,1,N);
        }
        //把heap中的数据复制回原数组source中
        System.arraycopy(heap,1,source,0,source.length);
    }

    //在heap堆中，对target处的元素做下沉，范围是0~range
    public static void sink(Comparable[] heap,int target,int range){

        while (2*target<=range){
            int max;
            if (2*target+1<=range){
                if (less(heap,2*target,2*target+1)){
                    max = 2*target+1;
                }else{
                    max = 2*target;
                }
            }else{
                max = 2*target;
            }

            if (!less(heap,target,max)){
                break;
            }

            exch(heap,target,max);
            target = max;
        }
    }
}
